/*
 *https://leetcode.cn/problems/number-of-digit-one/description/
 *面试题 17.06. 2出现的次数
 *数位DP
*/

class Solution {
public:
  int numberOf2sInRange(int n) {
      int k = 1000000000;

      int ans = 0, sum = 0;  
      while(k){
          int d=  n/k%10; //当前位的值
          if(d < 2) {
              ans += sum*k;
          } else if(d == 2){
              ans += sum*k+ n%k+1;
          }else {
              ans += (sum+1)*k;
          }
          k /= 10;
          sum  = sum*10 + d;    //当前位左侧的数值
      }
      return ans;
  }
};